package union;

import java.util.concurrent.Callable;

/**
 * @Author: LDeng
 * @Date: 2021-03-31 16:44
 */
//QuickUnion 基于size的优化 ， size小的合并到size大的
public class UnionFind_QU_S extends UnionFind_QU{

    private int[] sizes;

    public UnionFind_QU_S(int capacity) {
        super(capacity);
        sizes=new int[capacity];
        for (int i = 0; i < sizes.length; i++) {
            sizes[i]=1;//初始是1
        }
    }
    //合并v1,v2所在的集合
    //将v1的根节点合并到v2的根节点
    @Override
    public void union(int v1, int v2) {
        int p1=find(v1);
        int p2=find(v2);
        if(p1==p2) return;
        if(sizes[p1]<sizes[p2]){//以p1为根节点的元素数量小于以p2为根节点的元素数量
            parents[p1]=parents[p2];
            sizes[p2]=sizes[p2]+sizes[p1];//跟新p2的size
        }else{
            parents[p2]=parents[p1];
            sizes[p1]=sizes[p1]+sizes[p2];
        }
    }
}
